package sliding_window

//nSumTarget nSum 通用解法，调用此函数之前，一定要先给nums排序。因为nSumTarget是一个递归函数
// 只要数组有序，就应该想到双指针技巧。
// 如果在nSumTarget函数里调用排序函数，那么每次递归调用都会进行没有必要的排序，效率会很低
func nSumTarget(nums []int, n int, start int, target int) [][]int {
	sz := len(nums)
	var result [][]int

	//入参判断：至少是2Sum且数组大小不应该小于n
	if n < 2 || sz < n {
		return result
	}

	// 2sum 是基础
	if n == 2 {
		//利用双指针操作
		lo := start
		hi := sz - 1

		for lo < hi {
			sum := nums[lo] + nums[hi]

			//定住首位两个值，便于去重操作
			left := nums[lo]
			right := nums[hi]

			if sum < target {
				//去重并移动lo指针
				for lo < hi && nums[lo] == left {
					lo++
				}
			} else if sum > target {
				//去重并移动hi指针
				for lo < hi && nums[hi] == right {
					hi--
				}
			} else {
				//加入结果集
				result = append(result, []int{left, right})
				//去重
				for lo < hi && nums[lo] == left {
					lo++
				}

				for lo < hi && nums[hi] == right {
					hi--
				}
			}

		}
	} else {
		// n>2 时，递归计算(n-1)Sum 的结果
		for i := start; i < sz; i++ {
			subResult := nSumTarget(nums, n-1, i+1, target-nums[i])
			for _, arr := range subResult {
				// (n-1)Sum 需要加上nums[i] 就是nSum
				arr = append(arr, nums[i])
				result = append(result, arr)
			}
			//去重
			for i < sz-1 && nums[i] == nums[i+1] {
				i++
			}
		}
	}
	return result
}
